#pragma once
#include "tools.h"
#include "cdirenderlist.h"

template<typename C, typename V>
struct Node
{
  C     m_CompareValue;
  V     m_Value;
  Node* m_left;
  Node* m_right;
  
  Node( Node& node )
  {
    m_CompareValue = node.CompareValue;
    m_Value = node.m_Value;
  }

  Node( C compareValue, V value ) 
    : m_right( NULL ), 
      m_left( NULL ),
      m_CompareValue( compareValue ),
      m_Value( value )
  {
  }

  ~Node() 
  { 
    CLEAN_PTR( m_left );
    CLEAN_PTR( m_right );
  }
};

template<typename C, typename V>
class CdiBinaryTree 
/*  : public CdiRenderList */
{
  void Setup();
  bool AddNodeAux( Node<C,V>*& current, Node<C,V>* newNode);

protected:
  Node<C,V>*  m_root;
  size_t      m_count;
  bool        m_bAllowRepeats;

public: // Constructors
  CdiBinaryTree();
  virtual ~CdiBinaryTree();

public: // Methods
  bool AddNode( Node<C,V>* node );
  bool AddNode( C compare, V value);
  bool RemoveNode( Node<C,V>& node );
  bool RemoveAllNodes();
  Node<C,V>* FindNode( C findItem );
  Node<C,V>* FindNode( V findItem );

public: // Properties
  inline size_t GetCount() const { return m_count; } 
};

// ----------------------------------------------------------------
// Implementation
// ----------------------------------------------------------------

template<typename C, typename V>
bool CdiBinaryTree<C,V>::AddNode( Node<C,V>* node )
{
  return AddNodeAux( m_root, node );
}

template<typename C, typename V>
bool CdiBinaryTree<C,V>::AddNode( C compare, V value)
{
  return AddNode( new Node<C,V>( compare, value ) );
}

template<typename C, typename V>
bool CdiBinaryTree<C,V>::AddNodeAux( Node<C,V>*& current, Node<C,V>* newNode)
{
  if( current == NULL ) 
  {
    current = newNode;
  }
  if( current->m_CompareValue > newNode->m_CompareValue )
  {
    return AddNodeAux( current->m_right, newNode );
  }
  else
  {
    return AddNodeAux( current->m_left, newNode );
  }
}

template<typename C, typename V>
CdiBinaryTree<C,V>::CdiBinaryTree()
{
  Setup();
}

template<typename C, typename V>
CdiBinaryTree<C,V>::~CdiBinaryTree(void)
{
  CLEAN_PTR( m_root );
}

template<typename C, typename V>
void CdiBinaryTree<C,V>::Setup()
{
  m_bAllowRepeats = false;
  m_count         = 0;
  m_root          = NULL;
}